给定一个节点数为n的无序单链表,对其按升序排序。
数据范围:,保证节点权值在之内。
要求:空间复杂度 ,时间复杂度
function sortInList( head ) { let p = head const arr = [] while(p){ arr.push(p.val) p = p.next } const res = quickSort(arr,0,arr.length-1) let i = 0 p = head while(p){ p.val = res[i++] p = p.next } return head } const quickSort = (arr, low, high) => { if (low < high) { let par = partition(arr, low, high) quickSort(arr, low, par - 1) //注意下标起始,否则会造成死循环 quickSort(arr, par + 1, high) } return arr } const partition = (arr, low, high) => { let pivot = arr[low] while (low < high) { while (arr[high] > pivot && high > low) { high-- } arr[low] = arr[high] while (arr[low] <= pivot && high > low) { low++ } arr[high] = arr[low] } arr[low] = pivot return low }
/* * function ListNode(x){ * this.val = x; * this.next = null; * } */ /** * * @param head ListNode类 the head node * @return ListNode类 */ function sortInList( head ) { // write code here let length = 0 let cur = head while(cur){ length++ cur = cur.next } for(let i=0;i<length;i++){ cur = head while(cur&&cur.next){ if(cur.val>cur.next.val){ let temp = cur.val cur.val = cur.next.val cur.next.val = temp } cur = cur.next } } return head console.log(length) } module.exports = { sortInList : sortInList };
/* * function ListNode(x){ * this.val = x; * this.next = null; * } */ /** * * @param head ListNode类 the head node * @return ListNode类 */ function sortInList(head) { // write code here let p = head let a = [] while (true) { a.push(p.val) if (p.next == null) break p = p.next } a.sort((a, b) => a - b) let head2 = new ListNode(a[0]) p = head2 for (let i = 1; i < a.length; i++) { p.next = new ListNode(a[i]) p = p.next } return head2 } module.exports = { sortInList: sortInList };
function sortInList( head ) { // write code here const arr = [] let cur = head while (cur) { arr.push(cur.val) cur = cur.next } const newHead = { next: null } let newCur = newHead arr.sort((a,b) => a - b).forEach(item => { newCur.next = { val: item, next: null } newCur = newCur.next }) return newHead.next }